1. Field of the Invention
The present invention relates to a circuit usable for encrypting information, and specifically to a small-scale encryption key generation circuit for generating a round sub key used in an encryption algorithm referred to as “SAFER+”.
2. Description of the Related Art
An algorithm for encrypting information, known as “SAFER+” developed by Cylink Corp., has been made public. “SAFER+” is shown in FIG. 20 and is represented by reference numeral 1. The SAFER+ encryption algorithm 1 encrypts pre-encrypted 128-bit input data (plaintext) into a 128-bit encrypted text, using an encryption key having a bit length of 128, 192 or 256 bits.
The SAFER+ encryption algorithm 1 uses a round sub key generation circuit 2 for generating 17 round sub keys when the encryption key has 128 bits, 25 round sub keys when the encryption key has 192 bits, and 33 round sub keys when the encryption key has 256 bits; and an encryption circuit 3 for encrypting plaintext using the round sub key generated by the round sub key generation circuit 2.
In this algorithm, a calculation process is divided into stages referred to as “rounds”. The number of rounds is 8 when the encryption key has 128 bits, 12 when the encryption key has 192 bits, and 16 when the encryption key has 256 bits. Each round is further divided into two sub rounds, and only the final round is divided into three sub rounds. Accordingly, the number of sub rounds is 17 when the encryption key has 128 bits, when the encryption key has 192 bits, and 33 when the encryption key has 256 bits. A 128-bit round sub key is generated for each sub round.
FIG. 21 illustrates an algorithm for generating 17 round sub keys in the case where the encryption key has 128 bits. FIG. 22 illustrates an algorithm for generating 25 round sub keys in the case where the encryption key has 192 bits. FIG. 23 illustrates an algorithm for generating 33 round sub keys in the case where the encryption key has 256 bits. Among these algorithms, the algorithm for the case where the encryption key has 128 bits will be described with reference to FIG. 21.
The algorithm shown in FIG. 21 is for generating 17 round sub keys K1 through K17 from a 128-bit encryption key. Square boxes numbered “1”, “2”, . . . “15” and “16” each represent 8 bits of the 128-bit input encryption key. Among the 128 bits (i.e., 16 bytes), the lowest byte is assigned to the box numbered “1”, and the highest byte is assigned to the box numbered “16”. The least significant bit among the 128 bits is the lowest bit of the lowest byte represented by the box numbered “1”, and the most significant bit is the highest bit of the highest byte represented by the box numbered “16”. As a first round sub key K1, the 128-bit encryption key is output as it is.
In order to generate a round sub key K2 for the second sub round, the 17th byte is produced as follows. The input 128-bit encryption key is divided into 16 bytes, and an exclusive OR (XOR) of information at the same bit positions in the 16 bytes is found. The resultant value is defined as representing the information for the respective bit position in the 17th byte.
Then, 3-bit rotation is performed in each of the 17 bytes. Namely, for example, 8 bits of {7, 6, 5, 4, 3, 2, 1, 0} are rotated leftward by 3 bits, thereby obtaining {4, 3, 2, 1, 0, 7, 6, 5}. As a round sub key Kj for the jth sub round, information represented by the jth byte is first output as the lowest byte. Then, (j+1)th byte, (j+2)th byte, . . . , (j+15)th byte are output, to the total of 16 bytes. When (j+i) exceeds 17, the number of the byte obtained by subtracting 17 from (j+i) is output. In the case of, for example, the round sub key K15, bytes {15, 16, 17, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13} are selected in this order and output sequentially. Then, a bias value Bj is added to the information represented by the bytes output in this order. The bias value Bj is a fixed value represented by 128 bits, which is determined by a sub round number j. The bias value Bj and the selected value are added together so that it is not necessary to consider carry-over for each byte. Where the ith byte of the bias value Bj is Bj[i], the lowest byte of the round sub key K15 is obtained by adding the information represented by the 15th byte of an internal register and B15[0]. According to the addition for which carry-over need not be considered for each byte, when the addition result α≦255, α is set as the addition result as it is; and when the addition result α>255, (α−256) is set as the addition result.
As described above, for round sub keys K2 through K17, 3-bit rotation, and output and addition of bias values from the jth byte to the (j+15)th byte are repeated, thereby generating the corresponding round sub keys.
As shown in FIGS. 22 and 23, a round sub key is generated from a 192-bit encryption key or a 256-bit encryption key in basically the same manner as the case of the 128-bit encryption key, except for the following differences. The number of bytes stored is larger. In addition, in the case of 128 bias, when the value of (j+1) exceeds 17, 17 is subtracted from (j+1). In the case of 192 bits, when the value of (j+1) exceeds 25, 25 is subtracted from (j+1). In the case of 256 bits, when the value of (j+1) exceeds 33, 33 is subtracted from (j+1).
Many other encryption algorithms have been proposed and made public in, for example, Japanese Laid-Open Publication No. 2000-39840. This publication does not include any specific examples of key generation. Japanese Laid-Open Publication No. 11-45049 discloses a key generation procedure, but the encryption algorithm described in this publication is different from SAFER+, which is used by the present invention.
The above-described algorithm for generating a round sub key has the following problems. When an encryption key is input, all the round sub keys are simultaneously calculated and output. Therefore, the scale of the circuit is inevitably large. This is easily understood because selectors are necessary for changing the bytes to be output for each round sub key, and because 16 times of (number of the round sub keys −1) adders are necessary; i.e., 256 adders are necessary when the encryption key has 128 bits, 384 adders are necessary when the encryption key has 192 bits, and 512 adders are necessary when the encryption key has 256 bits. Even in a structure shown in FIG. 24 in which round sub keys are output one by one, a similar problem occurs when all the round sub keys are calculated simultaneously. In FIG. 24, a round sub key generation circuit 2 includes an exclusive OR circuit 9 for calculating an exclusive OR of bits located at identical positions in different bytes of the encryption key, a register 10, a 3-bit rotation circuit 12, an output selector 14, adders 15, and a bias table 16.